COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\input macro[1,mps]
C00012 ENDMK
C⊗;
\input macro[1,mps]
\magnification\magstephalf
\baselineskip 14pt
\leftline{\sevenrm A70.Tex[254,MPS]\today}
\leftline{\copyright\sevenrm Robert W. Floyd, November 7, 1988}
\leftline{\sevenrm Unpublished Draft}
\bigskip
\noindent{\bf Undecidability of the Halting Problem, Oblivious Programs, and
Rice's Theorem}
\bigskip
\noindent{\bf Theorem}:  Let $A$ be any set, $M$ a Turing machine 
with an A-oracle.  Let predicate
$H(c,d)$ be true iff $c$ encodes a program for $M$ that accepts argument
$d$.  We show that no program for $M$ can compute $H$.
\medskip
\noindent{\bf Proof}:  Suppose some program $P↓1$ for $M$ did compute $H$.  
We could build around
it a program $P↓2$ that, on argument $x$, uses a simulation of $P↓1$ to 
determine $H(x,x)$.  Then if $H(x,x)$ were true, it would halt in a 
rejecting state, and if $H(x,x)$ were false it would halt in an accepting 
state.

Let $c↓2$ be the encoding of $P↓2$.  Look at what happens when $c↓2$ is taken
as the argument of $P↓2$.  $H(c↓2,c↓2)$ is true implies that
$P↓2$ accepts $c↓2$ (so does not accept $c↓2$), and $H(c↓2,c↓2)$ is false 
implies that $P↓2$ does not accept $c↓2$.
Either way we have a contradiction, traceable only to the assumption that there
is a program for $M$ that computes $H$.
\medskip
\noindent{\bf Corollary}:  There is no program for $M$ that determines for 
arguments $c$
and $d$ whether $c$ encodes a program for $M$ that halts (whether accepting
or rejecting) on argument $d$.  
\medskip
\noindent{\bf Proof}:  If there were such a program, it could be used to 
compute
$H(c,d)$.  If the program does not halt, it does not accept.  If it halts, it can
safely be simulated until accepting or rejecting.  But we know that no program
$M$ can compute $H(c,d)$, so no program for $M$ can determine which programs for
$M$ halt on which data.

The corollary is an example of what is called a {\it reducibility} argument.
If there is an algorithm to convert any question in a set $S↓1$, 
into some question in a set $S↓2$, then a program that answers arbitrary
questions in $S↓2$ can be made into a program that answers arbitrary
questions in $S↓1$. If there is no program that answers arbitrary questions
in $S↓1$, there can be no program that answers arbitrary
questons in $S↓2$.  In the jargon, if $S↓1$ is reducible to $S↓2$, and $S↓1$
is undecidable, so is $S↓2$.  The standard tactic for proving a class of 
questions undecidable is to reduce the class of halting problems to it.

Naturally, the preceding undecidability results carry over to Turing
machines without oracles, which are equivalent in most ways to Turing machines
with an oracle for the empty set.  (``Just say no'' is the oracle's
motto.)
If $A$ is any oracle, let $B$ be the set of pairs $\langle c,d \rangle$ for
which program $c$ for an A-machine halts on argument $d$.  Then a B-program
can decide membership in $B$, which no A-program can do.  A B-program can
also decide membership in $A$.  Given argument $x$, to find whether $x \in A$, the
B-program constructs an A-program that, ignoring input, puts $x$ into an
oracle queue, tests whether $x \in A$, halts if $x \in A$, but loops if
$x \not\in A$.  Then the B-program uses the B-oracle to determine whether
the program it has constructed halts or not, which is to say, whether
$x \in A$ or not.

We conclude:  for any oracle $A$, there is an oracle $B = J(A)$, the
 {\it jump} of $A$, such that
anything an A-program can do can be done by a B-program, but the B-program
can decide the halting problems of A-programs, which no A-program can do.
There is no ``best'' oracle; for any oracle there is a better one,
just as for any number there is a bigger one.

Call a TM program that uses no input device an {\it oblivious} program.  If
$H(c,d)$ is an arbitrary halting problem for a TM with input device, then
there is an oblivious program $c'$ that initially puts $d$ in a designated
part of its infinite store, then proceeds to simulate program $c$ for the
original machine on input $d$.  Any program that solves the halting problem for
oblivious programs would therefore solve the general halting problem,
so we conclude the halting problem restricted to oblivious programs is
undecidable.
\medskip
\noindent{\bf Rice's Theorem}

Let $Q(P)$ be any statement about the transfer relation $\tau↓p$ of program 
$P$ for some designated Turing machine.
\medskip
\noindent {\bf Examples}:

\item{$\bullet$}
$x \tau↓p y$, for particular $x$ and $y$.

\item{$\bullet$}
The image $x\circ \tau↓p$, or the converse image $\tau↓p \circ y$, is 
empty/finite/infinite/some particular set.

\item{$\bullet$}
$\tau↓p$ is a 
function/a partial function/transitive/an equivalence relation/a monotone~function~
/re\-cur\-sive.

\item{$\bullet$}
For each $x$, $x\circ\tau↓p$ is infinite/cofinite 
\medskip
\noindent Rice's Theorem states:  If
there is a program for which $Q$ is true, and one for which $Q$ is false, then 
there is no algorithm for $Q(P)$.
\medskip
\noindent{\bf Proof}:  Let $P↓0$ be the null program 
$\{\langle i→i,\, \hbox {noop}\rangle\}$
that runs forever.  Say $Q(P↓0)$ is true.  Let $P↓1$ be a program for which
$Q(P↓1)$ is false.  We now reduce the halting problem for oblivious Turing
machines to the decision problem for $Q$.  Given any program $P↓2$ for an
oblivious Turing machine, construct a program $P↓3$ that looks for a
computation of $P↓2$.  If and when it finds one, $P↓3$ executes the program
for $P↓1$, so if $P↓2$ halts, $\tau↓{P↓3} = \tau↓{P↓1}$ and $Q(P↓3) = Q(P↓1) =
\hbox {false}$.  If $P↓3$ never finds a computation of $P↓2$, $\tau↓{P↓3} =
\emptyset = \tau↓{P↓0}$ and $Q(P↓3) = Q(P↓0) = \hbox {true}$.  The halting 
problem
for $P↓2$ has been reduced to $Q(P↓3)$, which is therefore undecidable.
\medskip
\noindent {\bf Warning}:  Questions about proper subsets of the Turing machines
may well be decidable.  For example, it is decidable whether a NPDA accepts
infinitely many inputs.  Questions that are not about the transfer relation 
may also be decidable.  For example, whether the number of states is odd,
or whether the machine has a nine-step computation, are decidable.
\bye